Digraphs & orientations.md (1395B)
1 +++ 2 title = 'Digraphs & orientations' 3 +++ 4 # Digraphs & orientations 5 Directed graphs: 6 7 - to convert graph to digraph, represent each edge with two equally weighted arcs 8 - digraph D consists of sets V(D) vertices and A(D) arcs 9 - arc \<u,v> joins vertex u (tail) to head v 10 - has indegree and outdegree, where the sum of all outdegrees is the same as the sum of all indegrees, which equals the number of arcs in D. 11 - adjacency matrix is not symmetric 12 - strict if ∀ u,v: (A[u,v]) ≤ 1 and A(u,u)=0 13 - in english: no duplicate edges between vertices, no loops 14 15 Connectivity with digraphs: 16 17 - strongly connected: there is a directed path "there and back" between any two vertices 18 - weakly connected: the underlying graph is connected (i.e. if all edges were made undirected, the graph would be connected) 19 - strongly connected digraphs form strongly connected components 20 - vertex v is reachable from u if there is a path (u,v) 21 - algorithm for reachability: 22 - Rt(u) is the set of reachable vertices from u, found after t steps. 23 - steps: 24 25 1. Set t ← 0 and R0(u) ← {u} 26 2. Construct set Rt+1(u) ← Rt(u) Uv ∈ Rt(u) Nout(v) 27 28 3. If Rt+1(u) = Rt(u), stop: R(u) ← Rt(u). Else, increment t and repeat step 2. 29 30 Orientations 31 32 - orientation of a simple graph is a digraph where you give every edge a direction 33 - there is strongly connected orientation iff λ(G) ≥ 2